#include<bits/stdc++.h>
using namespace std;
#define add(x,y) edge[++tail]=(dd){head[x],y},head[x]=tail;
struct dd{
    int ne,to;
}edge[10010];
int n,m,w[303],v[303],f[303][303];
int head[303],tail,w_tot[303];
void dfs(int t){
    f[t][w[t]]=v[t];
    for(int i=head[t];i;i=edge[i].ne){
        dfs(edge[i].to);
        for(int k=m;k>=w[t];k--)
        	for(int j=m-k;j>=0;j--)
                f[t][k+j]=max(f[t][k+j],f[t][k]+f[edge[i].to][j]);
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin>>m>>n;
    for(int i=1,x,y,j;i<=n;i++){
        cin>>w[i]>>y;
        v[i]=w[i]*y;
        cin>>j;
        add(j,i);
    }
    dfs(0);
    cout<<f[0][m];
}